package com.mgq.algorithm.twotree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 序列化树
 */
public class SerializeTree {
    /**
     * 先序序列化
     *
     * @param root
     * @return
     */
    public static String serializeTree(TreeNode root) {
        if (root == null) {
            return "#_";
        }
        String res = root.val + "_";
        //添加左树的序列化内容
        res += serializeTree(root.left);
        //添加右树的序列化内容
        res += serializeTree(root.right);
        return res;
    }

    public static TreeNode deserializeTree(String pre) {
        String[] array = pre.split("_");
        Queue<String> queue = new LinkedList<>(Arrays.asList(array));
       return rebuildTree(queue);
    }

    public static TreeNode rebuildTree(Queue<String> queue) {
        String value = queue.poll();
        if (value.equals("#")) {
            return null;
        }
        //先建头节点
        TreeNode treeNode = new TreeNode(Integer.parseInt(value));
        //再建左子树
        treeNode.left=rebuildTree(queue);
        //在建右子树
        treeNode.right = rebuildTree(queue);
        return treeNode;
    }
}
